package sword.T36;

/**
 * @Author: 18362
 * @Create: 2022-04-08 15:04:00 星期五
 */

class Solution {

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };

    private Node tail;

    public Node treeToDoublyList(Node root) {
        if (root == null)
            return root;
        inorder(root);
        Node head = root;
        while (head.left != null)
            head = head.left;
        head.left = tail;
        tail.right = head;
        return head;
    }

    private void inorder(Node root) {
        if (root == null)
            return;
        inorder(root.left);
        if (tail != null) {
            tail.right = root;
            root.left = tail;
        }
        tail = root;
        inorder(root.right);
    }
}